Міністерство освіти і науки України Вінницький національний технічний університет Факультет інформаційних технологій і комп’ютерної інженерії Кафедра комп’ютерних наук  Лабораторна робота №2З дисципліни: Теорія алгоритмів Тема: «Аналіз сортування алгоритму методом прямого вибирання»  Вінниця, 2017 Аналіз сортування алгоритму методом прямого вибирання Мета: проаналізувати складність алгоритму методом прямого вибирання, практично та аналітично. Навчитись оцінювати асимптотичну складність алгоритму. Ідея алгоритму: Серед n елементів масиву вибирається найменший. Він міняється місцями з першим елементом a1. Далі цей процес повторюється із рештою n - 1 елементами, n – 2 елементами і т. д. доти, поки не залишиться один, найбільший елемент. Такий алгоритм, у певному смислі, протилежний алгоритму сортування вставками. В останньому випадку на кожному кроці розглядається тільки один черговий елемент вихідної послідовності та всі елементи готової послідовності, серед яких відшуковується точка вставки; при прямому виборі для пошуку одного елементу з найменшим ключем проглядаються всі елементи вихідної послідовності і знайдений розташовується як черговий елемент у готову послідовність. Час роботи алгоритму: Як і у випадку сортування вставками, склавши внески всіх рядків отримаємо час виконання в загальному випадку: Відсортований масив: Цей випадок є найсприятливіший, оскільки не виконуються блоки 6 і 7, а отже час виконання буде найменшим. Відсортований у зворотному напрямку масив: Цей випадок є найнесприятливіший, оскільки кожен елемент масиву потрібно переміщати, а отже час виконання буде найбільший. Псевдокод алгоритму сортування прямим вибором: Блок-схема алгоритму сортування прямим вибором: Код програми: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Diagnostics; namespace _1234 { class Program { static void Main(string[] args){ // Створення масиву// Random zap = new Random();//для отримання випадкових цілих чисел Console.WriteLine("Введiть кiлькiсть елементiв масива:"); int a = Convert.ToInt32(Console.ReadLine());//конвертуєм змінну а в int Stopwatch watch0 = new Stopwatch(); watch0.Start(); int[] arr1 = new int[a]; Console.WriteLine("Невідсортований массив:"); //створюєм масив for (int q = 0; q < a; q++) { arr1[q] = zap.Next(1, 100); Console.Write(arr1[q] + " "); } watch0.Stop(); Console.WriteLine("\nЧас виконання програми в мілесекундах : " + watch0.ElapsedMilliseconds + "mc.\r\n"); //Сортування масиву// Stopwatch watch = new Stopwatch(); //для визначення часу виконання масиву watch.Start(); int min = 0, temp = 0; for (int i = 0; i < a - 1; i++) //сортуємо масив { min = i; for (int j = i + 1; j < a; j++) { if (arr1[j] < arr1[min]) { min = j; } } temp = arr1[i]; arr1[i] = arr1[min]; arr1[min] = temp; } Console.WriteLine("\nВiдсортований масив"); for (int i = 0; i < arr1.Length; i++) { Console.Write(arr1[i] + " "); //виводимо масив } watch.Stop(); Console.WriteLine("\nЧас виконання програми в мілесекундах : " + watch.ElapsedMilliseconds + "mc.\r\n"); //Сортування масиву у зворотньому напрямку// Stopwatch watch1 = new Stopwatch(); //для визначення часу виконання масиву watch1.Start(); int min1 = 0, temp1 = 0; for (int i = 0; i < a - 1; i++) //сортуємо масив ...